#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include "long_int_t.h"

long_int_t::long_int_t(int num)
{
   digits_.push_back(num);
}

long_int_t::long_int_t(const std::vector<int> &digits) : digits_(digits)
{
}

long_int_t& long_int_t::operator *=(const long_int_t& b)
{
   size_t len_a = digits_.size();
   size_t len_b = b.digits_.size();
   long_int_t c = long_int_t();
   c.digits_.resize(len_a + len_b);
   for (size_t i = 0; i < len_a; i++)
   {
      long long t = 0;
      for (size_t j = 0; j < len_b; j++)
      {
         t += c.digits_[i + j] + (long long)digits_[i] * b.digits_[j];
         c.digits_[i + j] = (int)(t % BASE);
         t /= BASE;
      }
      size_t j = len_b + i;
      while (t != 0)
      {
         c.digits_[j] = (int)t % BASE;
         t = t / BASE;
         j++;
      }
   }
   c.cut_zeroes();
   digits_ = c.digits_;
   return *this;
}

long_int_t& long_int_t::operator -=(const long_int_t& q)
{
   long_int_t b = q;

   size_t len_a = digits_.size();
   size_t len_b = b.digits_.size();

   for (size_t i = 0; i < len_a; i++)
   {
      int x;
      if (i < len_b)
         x = b.digits_[i];
      else 
         x = 0;
      digits_[i] -= x;
      if (digits_[i] < 0)
      {
         digits_[i] += BASE;
         digits_[i + 1] -= 1;
      }
   }
   cut_zeroes();
   return *this;
}

long_int_t& long_int_t::operator /=(const long_int_t& divider)
{
   *this = divide_with_remainder(divider).first;
   return *this; 
}

long_int_t& long_int_t::operator %=(const long_int_t& divider)
{
   *this = divide_with_remainder(divider).second;
   return *this; 
}

long_int_t& long_int_t::operator +=(const long_int_t& b)
{
   size_t len_a = digits_.size();
   size_t len_b = b.digits_.size();
   long long remainer = 0;
   for (size_t i = 0, len = std::max(len_a, len_b); i < len; i++)
   {
      int x, y;
      if (i >= len_a)
         x = 0;
      else
         x = digits_[i];
      if (i >= len_b)
         y = 0;
      else
         y = b.digits_[i];
      remainer = x + y + remainer;
      if (i < len_a)
         digits_[i] = (int)(remainer % BASE);
      else
         digits_.push_back((int)(remainer % BASE));
      remainer /= BASE;
      }

      if (remainer != 0) {
      digits_.push_back((int)remainer);
   }
   return *this;
}

bool long_int_t::operator ==(const long_int_t &b) const
{
   return compare_to(b) == 0;
}

bool long_int_t::operator >(const long_int_t &b) const
{
   return compare_to(b) > 0;
}

bool long_int_t::operator !=(const long_int_t &b) const
{
   return compare_to(b) != 0; 
}

bool long_int_t::operator >=(const long_int_t &b) const
{
   return compare_to(b) >= 0;
}

bool long_int_t::operator <(const long_int_t &b) const
{
   return compare_to(b) < 0;
}

std::pair<long_int_t, long_int_t> long_int_t::divide_with_remainder(const long_int_t &q) const
{
   long_int_t a = *this;
   long_int_t b = q;
   int shift = a.digits_.size() - b.digits_.size();
   if (shift < 0) 
      shift = 0;
   b <<= shift;
   std::vector<int> ans;
   while (shift >= 0)
   {
      int p = a.find_digit_divisor(b);
      ans.push_back(p);
      long_int_t tmp = b;
      tmp *= p;
      a -= tmp;
      b >>= 1;
      shift--;
   }
   reverse(ans.begin(), ans.end());
   b = static_cast<long_int_t>(ans);
   b.cut_zeroes();
   return std::make_pair(b , a);
}

  
int long_int_t::find_digit_divisor(const long_int_t &q) const 
{
   if (*this < q)
      return 0;
   int l = 0, r = BASE, m;
   while (l + 1 != r)
   {
      m = (l + r) / 2;
      long_int_t tmp = q;
      tmp *= m;
      if (*this < tmp)
         r = m;
      else
         l = m;
   }
   return l;
}

void long_int_t::cut_zeroes() 
{
   int len = digits_.size();
   while (len > 1 && digits_.back() == 0)
   {
      digits_.pop_back();
      len--;
   }
}

int long_int_t::compare_to(const long_int_t &a) const
{
   int is_reverse = 1;
   if (digits_.size() != a.digits_.size())
      return (digits_.size() - a.digits_.size()) * is_reverse;
   int i = digits_.size() - 1;
   while ((i >= 0) && (digits_[i] == a.digits_[i]))
   {
      i--;
   }
   if (i == -1)
      return 0;
   return (digits_[i] - a.digits_[i]) * is_reverse;
}

long_int_t& long_int_t::operator <<=(int shift)
{
   if (shift <= 0)
      return *this;
   std::vector<int> new_digits;
   new_digits.reserve(shift + digits_.size());
   for (int i = 0; i < shift; i++)
   {
      new_digits.push_back(0);
   }
   for (size_t i = 0; i < digits_.size(); i++)
   {
      new_digits.push_back(digits_[i]);
   }
   digits_ = new_digits;
   return *this;
}

long_int_t& long_int_t::operator >>=(size_t shift)
{
   if (shift >= digits_.size())
   {
      digits_.clear();
      digits_.push_back(0);
   } 
   else
   {
      digits_.erase(digits_.begin(), digits_.begin() + shift);
   }
   return *this;
}


std::ostream& operator <<(std::ostream& output, const long_int_t a)
{
   output << a.digits_[a.digits_.size() - 1];
   for (size_t i = 0, len = a.digits_.size() ; i < len - 1; i++)
   {
      int tmp = a.BASE / 10;
      int x = a.digits_[len - i - 2];
      while (tmp > 0)
      {
         output << x / tmp;
         x %= tmp;
         tmp /= 10;
      }
   }
   return output;
}

std::istream& operator >>(std::istream& input, long_int_t& a)
{
   std::string number;
   input >> number;
   if (number == "0")
   {
      a = long_int_t();
      return input;
   }
   a.digits_.clear();
   int x = 0;
   int tmp = 1;
   for (int i = number.length() - 1; i >= 0; i--) 
   {
      x += (number[i] - '0') * tmp;
      tmp *= 10;
      if (tmp == a.BASE)
      {
         a.digits_.push_back(x);
         tmp = 1;
         x = 0;
      }
   }
   if (x != 0)
      a.digits_.push_back(x);
   return input;
}